package com.linwen.excise.leetcode;


import java.util.*;

public class _1两数之和 {

    /**
     给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，
     并返回它们的数组下标。
     你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     **/

    public static void main(String[] args) {
        int[] params= new int[]{2,7,11,15};
        int target = 9;
        int []result = function2(params,target);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]+" ");
        }
    }
    //使用map的key来匹配target-nums[i]的值。如果有重复数字，可以将重复数字的位数存在一个数组中
    private static int[] function2(int[] nums, int target) {
        int []result = new int [2];
        Map<Integer,Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            int temp = target-nums[i];
            if(map.containsKey(temp)){
                result[0] = map.get(temp);
                result[1] = i;
            }else {
                map.put(nums[i],i );
            }
        }
        return  result;
    }

    /**
     * 暴力破解方法  时间复杂度n的平方
     * @param params
     * @param target
     * @return result
     */
    private static int[] function1(int[] params, int target) {
        int []result = new int [2];
        //暴力破解 时间复杂度n的平方
         Set<Integer> set = new HashSet<Integer>();
         for(int i=0;i<params.length;i++) {
             for (int j = 0; j < params.length; j++) {
                 if (i == j) {
                     continue;
                 }
                 if (params[i] + params[j] == target) {
                     set.add(i);
                     set.add(j);
                 }
             }
         }
         //set转list
         List<Integer> list = new ArrayList(set);
         for(int i=0;i<list.size();i++) {
             result[i] = list.get(i);
         }
        return  result;
    }
}
